The invention relates to presenting a node-link structure in which modification occurs.
Lamping, J. and Rao, R., xe2x80x9cThe Hyperbolic Browser: A Focus+Context Technique for Visualizing Large Hierarchiesxe2x80x9d, Journal of Visual Languages and Computing, Vol. 7, 1996, pp. 33-55, disclose techniques for displaying a hierarchy in which components diminish in size as they move outwards and the number of components grows exponentially with increasing radius. The display can be smoothly transformed to change the node at the center or focus. Animated transitions between different views maintain object constancy, helping a user assimilate changes. For quick redisplay, less of a fringe is drawn, lines can be drawn rather than arcs, and text can be dropped during animation. Lamping et al., U.S. Pat. No. 5,619,632, disclose a browser that employs similar techniques for presenting a node-link structure and mention that a browser could be used in editing structures.
Matsuura, T., Taniguchi, K., Masuda, S., and Nakamura, T., xe2x80x9cA Graph Editor for Large Trees with Browsing and Zooming Capabilitiesxe2x80x9d, Systems and Computers in Japan, Vol. 24, No. 8, 1993, pp. 35-46, disclose a library program which allows direct manipulation of a large tree on a display. When a node or subtree is added or deleted, the data structure is updated; the layout for each node is calculated based on the graph layout algorithm, and each node and edge is redrawn. When nodes are added or deleted consecutively, a single update of the display can be performed after all the modifications have been made. A viewport includes a global view and a canvas, and updating depends on mode, which may be automatic update, partial update, or on demand update. Partial update resembles on demand update, but an intermediate display node is displayed temporarily.
Beaudet et al., U.S. Pat. No. 5,515,487, disclose selective display of portions of graphics by expanding and collapsing nodes in trees, directed acyclic graphs, and cyclic graphs. Nodes are selected for modification, all nodes connected to each selected node is assigned to a first set of nodes, and then each node is removed from the first set of nodes and assigned to a second set, together with any connected nodes that are not in the first set. The identified nodes are deleted from the display, and each node connected to a deleted node is highlighted, surrounded by an outline box, shown with outgoing arcs, or otherwise shown in a way that distinguishes collapsed nodes.
Windows NT Explorer is a program that can be used to see the hierarchy of folders on a disk drive. The hierarchy is presented as a list of items, with indentation showing which items are children of other items. Some folders are presented with plus signs (+), and if the user does a mouse click on a plus sign, more folders will be displayed. Windows NT also provides a similar program that can be used to see a hierarchy of network resources.
The invention addresses problems in presenting node-link structures that change.
A node-link structure can change in several situations. For example, if the structure is large, the data available at a given time may only define part of the structure. This may occur because data defining the complete structure has not yet arrived or because the structure is so large that memory is not large enough to hold a complete definition of it. In such cases, a partial structure is held in memory, to be changed as additional data arrives or is retrieved.
Another situation in which a node-link structure changes is when the structure is a partial version of an underlying structure. For example, the user may request that specified types of nodes or links be selected to obtain a filtered version. In response, a node-link structure is produced that omits nodes and links that are not selected by the filter criterion, allowing more space for nodes and links of interest. Or the structure can be a tree that represents an underlying directed graph (DG) structure in which there are multiple in-links to a node in the DG that in turn has children. In one approach, the DG node is represented by multiple parent nodes in the tree, each with one of the in-links, but the DG node""s children are represented with only one of the parent nodes in the tree. In response to user input, the parent node with which the children are represented can change, thus changing the tree structure (but not the DG).
Also, the underlying structure may itself change. For example, it may be modified in response to processes other than the browser through which it is being viewed. Or it may be modified in response to user requests through the browser interface.
A node-link structure that changes in any of these ways is referred to herein as a xe2x80x9cdynamic node-link structurexe2x80x9d. This term therefore includes not only underlying node-link structures that change, but also partial versions that change or are obtained differently from an underlying node-link structure, which may itself be either static or dynamic.
The presentation techniques described by Lamping and Rao and other conventional techniques can lead to problems with structure change during presentation. Typically, a new layout must be done for at least part of the changed structure and then it must be redisplayed. Therefore, when a change occurs in a structure being presented with such techniques, there is often an abrupt or discontinuous transition to a representation of the changed structure. In some cases, layout and redisplay is so slow that a user cannot effectively interact with the changed structure. Further, layout and redisplay do not provide a way to animate the transition from the old to the new structure, which would improve the user""s understanding of the transition. Therefore, many conventional presentation techniques only produce satisfactory results for static node-link structures, and are not suitable for dynamic node-link structures.
Some conventional presentation techniques can, however, animate transitions to expand or contract an item on a hierarchical list. These techniques are limited however to one modification, either an expansion or a contraction, and therefore are difficult to generalize to all transitions.
The invention alleviates problems in presenting dynamic node-link structures by providing techniques that make it easier for a user to understand a broader range of transitions. Each technique presents a sequence of representations, the first of which represents a first node-link structure and the last of which represents a second node-link structure that is a modified version of the first node-link structure. The elements shared by the first and last structures include a moving element represented by features that have different positions in the first and last representations. Between the first representation and the last representation, the techniques present at least one intermediate representation. Each representation in the sequence includes features representing a subset of the shared elements that includes the moving element. The feature representing the moving element has object constancy through the sequence of steps.
In one aspect of the invention, the second node-link structure is a modified version with at least one insertion and at least one deletion in the first node-link structure. For example, an element could be deleted from one position and inserted at another position. Therefore, techniques according to this aspect, referred to as xe2x80x9cdeletion and insertionxe2x80x9d herein, could be used to move an element or to make more complicated changes, in cluding multiple deletions and insertions.
Each of the new deletion and insertion t techniques presents a sequence of images in which the area of an element being deleted or inserted changes, either decreasing or increasing in each successive image. At the same time, compensating area changes occur in nearby elements. If the area changes are appropriately chosen, the sequence of images will produce the impression that, in deletion, nearby elements are closing in on the element being deleted and, in insertion, that the element being inserted is pushing nearby elements aside.
The sequence of images can also, in each case, provide an appropriate motion of an element being deleted or inserted. For example, in deletion of an element with a wedge-shaped area, the element being deleted can move out the open end of its wedge, can shrink along with its wedge, or can disappear before its wedge begins to shrink.
Yet other deletion and insertion techniques animate expansion or contraction of the descendants of a node. In expansion of a node""s descendants, the descendants can spread from the node; in contraction, the descendants can be d drawn into the node.
The deletion and insertion techniques can be implemented with a first subsequence of steps in which features representing elements are deleted and a second subsequence in which features representing elements are inserted. For example, to show an element in a new position, it can first be deleted at its previous position and then inserted at the new position.
Another aspect of the invention is based on the discovery of techniques for animating a transition in a two-dimensional display. According to these techniques, two moving elements follow paths that are not parallel straight lines. For example, the elements may be moving along curved paths, or the elements may be moving along independent non-parallel paths.
Yet another aspect of the invention is based on the discovery of techniques for concurrently animating separate changes in a node-link structure. According to these techniques, signals are received requesting at least two separate changes, and change data indicating the requested changes are obtained based on the signals. Then, the change data and a first data structure defining the node-link structure are used to obtain a second data structure defining a changed version of the node-link structure, and then representations can accordingly be presented.
The new techniques are advantageous because they make it easy for the user to understand a transition in a dynamic node-link structure. In addition, the new techniques can be implemented without the time-consuming computation necessary to perform layout and redisplay of a complete node-link structure instead, incremental layout and redisplay can be employed. As a result, a user is able to interact more effectively with a dynamic node-link structure.
The following description, the drawings, and the claims further set forth these and other aspects, objects, features, and advantages of the invention.